import entity.TreeNode;

import java.util.LinkedList;

public class CountCompleteTreeNodes {
    /*
    * 222. 完全二叉树的节点个数
    * 给你一棵 完全二叉树 的根节点 root ，求出该树的节点个数。
    * 完全二叉树 的定义如下：在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，
    * 并且最下面一层的节点都集中在该层最左边的若干位置。若最底层为第 h 层，则该层包含 1~ 2^h 个节点。
    *
    * 提示：
    * 树中节点的数目范围是[0, 5 * 10^4]
    * 0 <= Node.val <= 5 * 10^4
    * 题目数据保证输入的树是 完全二叉树
    * */
    public static void main(String[] args){

    }

    // 我的想法：一次层序遍历，解决问题
    public int mySolution(TreeNode root){
        if(root == null)
            return 0;
        LinkedList<TreeNode> deque = new LinkedList<>();
        deque.add(root);
        int res = 0;
        while (!deque.isEmpty()){
            int len = deque.size();
            while (len > 0){
                res++;
                TreeNode node = deque.pop();
                if(node.left != null) deque.add(node.left);
                if(node.right != null) deque.add(node.right);
                len--;
            }
        }
        return res;
    }

    // 递归，统计每个节点的子节点个数即可
    public int countNodes(TreeNode root){
        if(root == null)
            return 0;

        return 1 + countNodes(root.left) + countNodes(root.right);  // 1是节点自己
    }

    // 利用完全二叉树特性：完全二叉树节点数==2^层数-1
    // 递归过程中判断，子树为完全二叉树，则直接计算返回结果，能够避免继续继续向下递归
    public int countNodesPlus(TreeNode root){
        if(root == null)
            return 0;
        // 开始判断这是不是一颗完全二叉树
        int leftDepth = 0;
        int rightDepth = 0;
        TreeNode left = root.left;
        TreeNode right = root.right;
        while(left != null){
            leftDepth++;
            left = left.left;
        }
        while (right != null){
            rightDepth++;
            right = right.right;
        }
        if (leftDepth == rightDepth) // 确实是完全二叉树
            return (2 << leftDepth) -1;

        return 1 + countNodesPlus(root.left) + countNodesPlus(root.right);
    }
}
